/**
 * @file heap.cpp
 * @author xincz
 * @brief 
 * @version 0.1
 * @date 2021-05-27
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include "heap.h"


template <class T, class Compare>
Heap<T, Compare>::Heap() {
    _elems.push_back(T());
}

template <class T, class Compare>
Heap<T, Compare>::Heap(const std::vector<T>& elems) {
    _elems.push_back(T());
    for (size_t i=0; i<elems.size(); ++i) _elems.push_back(elems[i]);
    for (size_t i=parent(_elems.size()-1); i>0; --i) heapifyDown(i);
}

template<class T, class Compare>
size_t Heap<T, Compare>::root() const {
    return 1;
}

template<class T, class Compare>
size_t Heap<T, Compare>::leftChild(size_t currIndex) const {
    return 2*currIndex;
}

template<class T, class Compare>
size_t Heap<T, Compare>::rightChild(size_t currIndex) const {
    return 2*currIndex+1;
}

template<class T, class Compare>
size_t Heap<T, Compare>::parent(size_t currIndex) const {
    return currIndex / 2;
}

template<class T, class Compare>
bool Heap<T, Compare>::hasAChild(size_t currIndex) const {
    return _elems.size() > leftChild(currIndex);
}

template<class T, class Compare>
size_t Heap<T, Compare>::maxPriorityChild(size_t currIndex) const {
    size_t left = leftChild(currIndex);
    size_t right = rightChild(currIndex);
    if (right >= _elems.size()) return left;
    if (higherPriority(_elems[left], _elems[right])) return left;
    return right;
}

template<class T, class Compare>
void Heap<T, Compare>::heapifyDown(size_t currIndex) {
    if (hasAChild(currIndex)) {
        size_t maxChild = maxPriorityChild(currIndex);
        if (higherPriority(_elems[maxChild], _elems[currIndex])) {
            std::swap(_elems[maxChild], _elems[currIndex]);
            heapifyDown(maxChild);
        }
    }
}

template<class T, class Compare>
void Heap<T, Compare>::heapifyUp(size_t currIndex) {
    if (currIndex == root()) return;
    size_t parentIndex = parent(currIndex);
    if (higherPriority(_elems[currIndex], _elems[parentIndex])) {
        std::swap(_elems[currIndex], _elems[parentIndex]);
        heapifyUp(parentIndex);
    }
}

template<class T, class Compare>
T Heap<T, Compare>::pop() {
    T ret = _elems[root()];
    _elems[root()] = _elems.back();
    _elems.pop_back();
    heapifyDown(root());
    return ret;
}

template<class T, class Compare>
T Heap<T, Compare>::peek() const {
    return _elems[pop()];
}

template<class T, class Compare>
void Heap<T, Compare>::push(const T& elem) {
    _elems.push_back(elem);
    heapifyUp(_elems.size()-1);
}

template<class T, class Compare>
bool Heap<T, Compare>::empty() const {
    return (_elems.size() == 1);
}
